package com.lfg.leetcode.leetcode100;


import java.util.*;

public class No140wordBreak {

    public static void main(String[] args) {
//        List<String> ret = wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", new ArrayList<String>(Arrays.asList("a,aa,aaa,aaaa,aaaaa,aaaaaa,aaaaaaa,aaaaaaaa,aaaaaaaaa,aaaaaaaaaa".split(","))));
        List<String> ret = wordBreak("aaaaaaa", new ArrayList<String>(Arrays.asList("aaaa,aa,a".split(","))));
//        List<String> ret = wordBreak("catsanddog", new ArrayList<String>(Arrays.asList("cat,cats,and,sand,dog".split(","))));
        System.out.println(ret);
    }

    public static List<String> wordBreak(String s, List<String> wordDict) {
        if (null == s || null == wordDict || "".equals(s) || wordDict.isEmpty()) {
            return new ArrayList<>();
        }

        int length = s.length();
        List<String> ret = new ArrayList<>(length);

        wordBreak(s, length, wordDict, new ArrayList<>(length), ret);
        return ret;
    }

    public static void wordBreak(String s, int length, List<String> wordDict, List<String> data, List<String> ret) {

        if (s.length() == 0) {
            StringBuilder sb = new StringBuilder(2 * length);
            for (String str : data) {
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                sb.append(str);
            }
            ret.add(sb.toString());
            return;
        }
        if (!isWordBreak(s, wordDict)) {
            return;
        }
        for (String str : wordDict) {
            if (str.length() > s.length()) {
                continue;
            }
            String word = s.substring(0, str.length());
            if (str.equals(word)) {
                data.add(word);
                wordBreak(s.substring(str.length()), length, wordDict, data, ret);
                data.remove(data.size() - 1);
            }
        }
    }


    public static boolean isWordBreak(String s, List<String> wordDict) {
        if (null == s || null == wordDict || "".equals(s) || wordDict.isEmpty()) {
            return false;
        }

        int length = s.length();
        boolean[] ret = new boolean[length + 1];
        int minLength = length;
        int maxLength = 0;
        for (String str : wordDict) {
            maxLength = Math.max(maxLength, str.length());
            minLength = Math.min(minLength, str.length());
        }
        ret[0] = true;
        Set<String> set = new HashSet<>(wordDict);
        for (int i = 0; i < length; i++) {
            if (!ret[i]) {
                continue;
            }
            int end = i + maxLength;
            for (int endIndex = minLength + i; endIndex <= end && endIndex <= length; endIndex++) {
                if (set.contains(s.substring(i, endIndex))) {
                    ret[endIndex] = true;
                }
            }
            if (ret[length]) {
                return ret[length];
            }
        }

        return ret[length];
    }
}
